package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
	return isValidBST2(root, nil, nil)
}

func isValidBST2(root, min, max *TreeNode) bool {
	if root == nil {
		return true
	}
	if min != nil && root.Val <= min.Val {
		return false
	}
	if max != nil && root.Val >= max.Val {
		return false
	}
	return isValidBST2(root.Left, min, root) && isValidBST2(root.Right, root, max)
}

//
// 701. 二叉搜索树中的插入操作
//
func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return &TreeNode{
			Val: val,
		}
	}
	// BST 中一般不会插入已存在元素
	// if root.Val == val {}
	if root.Val < val {
		root.Right = insertIntoBST(root.Right, val)
	}
	if root.Val > val {
		root.Left = insertIntoBST(root.Left, val)
	}
	return root
}

//
// 450. 删除二叉搜索树中的节点
//
func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == key {
		// 1 当前节点是叶结点
		if root.Left == nil && root.Right == nil {
			return nil
		}
		// 2 当前节点是残疾节点
		if root.Left == nil {
			return root.Right
		}
		if root.Right == nil {
			return root.Left
		}
		// 3 当前节点是健全节点
		if root.Left != nil && root.Right != nil {
			minNode := getMin(root.Right)
			root.Val = minNode.Val
			root.Right = deleteNode(root.Right, minNode.Val)
			return root
		}
	} else if root.Val > key {
		root.Left = deleteNode(root.Left, key)
	} else if root.Val < key {
		root.Right = deleteNode(root.Right, key)
	}
	return root
}

func getMin(node *TreeNode) *TreeNode {
	for {
		if node.Left == nil {
			break
		}
		node = node.Left
	}
	return node
}

//
// 102. 二叉树的层序遍历
//
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	q := make([]*TreeNode, 0, 1)
	q = append(q, root)

	var res = [][]int{}

	for {
		size := len(q)
		if size == 0 {
			break
		}
		var levelRes = []int{}
		for i := 0; i < size; i++ {

			currentNode := q[0]
			// fmt.Printf("%v ", currentNode.Val)
			levelRes = append(levelRes, currentNode.Val)
			q = q[1:]

			if currentNode.Left != nil {
				q = append(q, currentNode.Left)
			}
			if currentNode.Right != nil {
				q = append(q, currentNode.Right)
			}
		}
		res = append(res, levelRes)
	}
	return res
}

func main() {
	t := produceATree()
	levelTraverse(&t)
	fmt.Println(levelOrder(&t))

	// fmt.Println(isValidBST(&t))
	// x := insertIntoBST(&t, 0)
	// fmt.Println(isValidBST(x))
	// y := deleteNode(x, 20)
	// fmt.Println(y)
	// levelTraverse(y)

}

// 输入一棵二叉树的根节点，层序遍历这棵二叉树
func levelTraverse(root *TreeNode) {
	if root == nil {
		return
	}
	q := make([]*TreeNode, 0, 1)
	q = append(q, root)

	for {
		size := len(q)
		if size == 0 {
			break
		}
		for i := 0; i < size; i++ {

			currentNode := q[0]
			fmt.Printf("%v ", currentNode.Val)
			q = q[1:]

			if currentNode.Left != nil {
				q = append(q, currentNode.Left)
			}
			if currentNode.Right != nil {
				q = append(q, currentNode.Right)
			}
		}
		fmt.Println()
	}
	fmt.Println()

}

func produceATree() TreeNode {
	/*
			3
			/ \
		   1  20
			 /  \
			15   22
	*/
	return TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val:   1,
			Left:  nil,
			Right: nil,
		},
		Right: &TreeNode{
			Val: 20,
			Left: &TreeNode{
				Val:   15,
				Left:  nil,
				Right: nil,
			},
			Right: &TreeNode{
				Val:   22,
				Left:  nil,
				Right: nil,
			},
		},
	}
}
